package arithmetic;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * @Author: Jie
 * @Date: 2019/1/16 10:47
 * @Function : 239. 滑动窗口最大值
 *
 * 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
 * 输出: [3,3,5,5,6,7]
 * 解释:
 *
 *   滑动窗口的位置                最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 *  1 [3  -1  -3] 5  3  6  7       3
 *  1  3 [-1  -3  5] 3  6  7       5
 *  1  3  -1 [-3  5  3] 6  7       5
 *  1  3  -1  -3 [5  3  6] 7       6
 *  1  3  -1  -3  5 [3  6  7]      7
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class A_06_SlidingWindowMax {
    public static void main(String[] args) {

        //思路 双端队列
        int [] nums = {1,3,-1,-3,5,3,6,7};
//        int[] nums = {1, 3};
//        int[] nums = {1,3,1,2,0,5};
        int[] result = maxSlidingWindow1(nums, 3);
//        int[] result = maxSlidingWindow_LeetCodeFast(nums, 3);
        System.out.println(result.toString());
        for (int number : result) {
            System.out.println(number);
        }
    }

    //思路：
    //cache list 左边最大值 ，is result ,
    // if (left < right ) poll
    // notify slidingWindow size int[] length
    private static int[] maxSlidingWindow1(int[] nums, int k)  {
        if (nums == null || nums.length <= 0 || k < 1)
            return new int[0];
        int[] result = new int[nums.length - k > 0 ? nums.length - k + 1 : 1];

        //存储 窗口数据的 index
        LinkedList<Integer>  window = new LinkedList<Integer>();

        for (int j = 0; j < nums.length; j++) {
            //移除窗口缓存中的左边的多余元素
            if (window.size() >0 && window.peek()+k<=j) {
                window.poll();
            }

            //比较元素，移除左边元素（如果 左边<右边）
            Iterator<Integer> iterator = window.iterator();
            while (iterator.hasNext()) {
                Integer index = iterator.next();
                if (nums[index] <= nums[j]) {
                    iterator.remove();
                }
            }

            // 加入新元素，结果
            window.addLast(j);//

            //结果：返回元素左边最大值,
            //数组比窗口大 情况1
            if (j >= k - 1) {
                result[j - k + 1] = nums[window.peek()];
            }
        }

        //数组比窗口小 情况2
        if (nums.length < k) {
            result[0] = nums[window.peek()];
        }
        return result;
    }




    //思路 缓存一个最大值，max 与索引 index
    //if (nums[i] >= max) {//优点，碰到新窗口 是Max值直接结束
    //缺点，碰到 后面新窗口的不是Max的值，需要把整个数据排序，原因值有一个 临时变缓存Max
    private static int[] maxSlidingWindow_LeetCodeFast(int[] nums, int k)  {
        // 这个算是比较容易想到的思路了，且速度也不慢。
        if (nums == null || nums.length <= 0 || k <= 0) {
            return new int[0];
        }

        int length = nums.length;
        int[] result = new int[nums.length > k ? nums.length - k + 1 : 1];

        //最大值索引
        int maxIndex = 0;
        //最大值
        int max = nums[0];

        //找到第一个窗口最大值
//        for (int i = 0; i < k; i++) {
        for (int i = 0; i < nums.length && i < k; i++) {//TODO 防止 窗口比 数据大
            if (nums[i] >= max) {
                max = nums[i];
                maxIndex = i;
            }
        }
        result[0] = max;
        //移动窗口
        for (int i = k; i < length; i++) {
            //更新索引与最大值
            if (nums[i] >= max) {//优点，碰到新窗口 是Max值直接结束
                max = nums[i];
                maxIndex = i;
            }
            //如果上一个最大值移动到窗口外，在当前窗口中找出最大值
            else if (i - k >= maxIndex) {
                //index 变为下一个窗口的起始位置
                maxIndex = i - k + 1;
                max = nums[i];
                //缺点，碰到 后面新窗口的不是Max的值，需要把整个数据排序，原因只有一个 临时变缓存Max
                for (int j = i - k + 1; j <= i ; j++) {
                    if (nums[j] >= max) {
                        max = nums[j];
                        maxIndex = j;
                    }
                }
            }
            result[i - k + 1] = max;
        }

        return result;
    }
}
